Stacks and Queues are two very commonly used dynamic data structures that provide us with a unique way of handling data. The usage of these types of data structures varies and depends on the problem as all other tools in software engineering.
Let’s get more deeply into each of these data structures to understand how they work and where we could use them.
Stack
A Stack data structure is a collection of data that implements a Last In First Out (LIFO) principle. In Java, stacks are an abstract class that extends the vector class.
To make it simpler imagine a bucket, add all items from the top and stack them up on top of each other. You only have access to the top of the stack. When you remove an item from the top of the stack, the item you get is the last item you added.
Stack has four basic methods:
- The push method which adds an item to the top of the stack
- The pop method which removes the item at the top
- The peek method which gets the item at the top without removing it from the stack
- The isEmpty method which s used to check if the stack is empty
Use cases
Generally, a common usage of the stack data structure is for a quick forward/backwards navigation within an app.
Let’s take for example an internet browser, on which we get a back navigational button. Keeping track of the URLs a user has visited is a good use case for a stack. With the URL of the current site a user is viewing, to be on the top of the stack we can move backwards by popping URLs from the stack.
Another cool usage is implementing an undo feature in text editors. We store previous text edits in a stack and go back through it.
Additionally, take a look at the code below that reverses a given string by utilizing a simple java stack data structure
Queue
A Queue data structure is a collection of data that implements a First In First Out (FIFO) principle. A Queue in Java is an interface, which means we need to implement it on a concrete class. Usually, we use it on LinkedList or PriorityQueue classes.
Queues provide as with access to the beginning and the end of the list, respectively called the head and the tail.
Simply imagine a tube where you add items in from one end and they come out the other end in the same order you added them.
Queues have three basic methods similar to stacks:
- The add method which adds an item through the tail of the queue, also known as enqueue method
- The poll method which gets and removes the first item on the head of the queue, also known as dequeue.
- The peek method which gets the item on the head but does not remove it from the queue
Use cases
Generally, we use a queue whenever we want to process items in the same order as they requested processing.
Some common usages of a queue data structure are when, for example, an application implements a first in first serve principle such as IO buffers and files IO asynchronous requests.
Other similar use cases we may want to use a queue, is when we share resources with other apps or systems such as CPU (i.e. multithreading) and DISK scheduling.
Queues are also used in searches such as a Breadth-First Search method of a graph or tree as well as in CACHE systems.
In general, it is a good practice to use a queue data structure when you have multiple requests to serve at once but not the ability to do so. It is fair to serve them in a FIFO principle.
To show you a practical example where we can use a queue, I wrote below a java method that searches a tree if it has a path to a given node.
Concluding
In this article, we covered what a Stack and a Queue data structures are, their principles and basic functionalities, as well as some common usage examples.
Stacks and Queues are very simple yet powerful tools that are now at your disposal to use in solving problems as you may find appropriate.
I hope you enjoyed this article and stay tuned for more!
